package a07_二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a25_二叉搜索树中的众数复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/27
 */
public class a25_二叉搜索树中的众数复习2 {

    public static void main(String[] args) {
        a25_二叉搜索树中的众数复习2 test = new a25_二叉搜索树中的众数复习2();
        TreeNode treeNode = new TreeNode(1,
                new TreeNode(1),
                new TreeNode(2,
                        null,
                        new TreeNode(2)
                        ));
        System.out.println(Arrays.toString(test.findMode(treeNode)));
    }

    public int[] findMode(TreeNode root) {
        traversal(root);
        return resultList.stream().mapToInt(i -> i).toArray();
    }

    private TreeNode prevNode;
    private int num = 0;
    private int maxNum = 0;
    private List<Integer> resultList = new ArrayList<>();

    private void traversal(TreeNode node){
        if (node == null) {
            return;
        }

        traversal(node.left);

        if (prevNode != null) {
            if(prevNode.val == node.val){
                num++;
            }else {
                num = 1;
            }
            if(num > maxNum){
                resultList.clear();
                maxNum = num;
                resultList.add(node.val);
            }else if(num == maxNum){
                resultList.add(node.val);
            }
        }else {
            num++;
            maxNum = 1;
            resultList.add(node.val);
        }
        prevNode = node;

        traversal(node.right);
    }
}
